海战
题目 海战
思路分析
这道题的难点在于判断是否有船相邻。 如果图是不和法的，一定存在如下结构：
. #
.
.
. #
即在一个2*2的方格中有三个#
洛谷太傻逼了 一堆runtime error
下面这个写法不是用洪水灌溉
有个想法是 先用洪水灌溉找到连通块 再对每一个连通块进行拆解？
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1010;
char g[N][N];
int n,m;
int dx[4]={0,-1,1,0};
int dy[4]={-1,0,0,1};
bool isVaild(int x,int y){
return x>=1 && x<=n && y>=1 && y<=m;
}
int dfs(int x,int y){
g[x][y]='*';
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(isVaild(nx,ny) && g[nx][ny]=='#')
dfs(nx,ny);
}
}
bool check(int i,int j){
int c=0;
if(g[i][j]=='#')
c++;
if(g[i+1][j]=='#')
c++;
if(g[i][j+1]=='#')
c++;
if(g[i+1][j+1]=='#')
c++;
if(c==3)
return false;
return true;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
int s=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i<n && j<m && !check(i,j)){
cout<<"Bad placement.";
return 0;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]=='#'){
s++;
dfs(i,j);
}
}
}
cout<<"There are "<<s<<" ships.";
return 0;
}
💬 评论